package com.lihui.heap;

import java.util.Arrays;

/**
 * 功能描述
 *
 * @author wileda
 * @date 2022/11/04  10:38
 */
public class Heap {
    private int[] elementDate;
    private int size;
    private int DEFAULT_CAPACITY = 10;

    public Heap() {
        this.elementDate =new int[DEFAULT_CAPACITY];
        this.size = 0 ;
    }

    public Heap(int [] array) {
        // 重新复制数组，防止外部修改数组对heap里数据的影响
        this.elementDate = Arrays.copyOf(array, array.length);
        this.size = elementDate.length;
        // 向下调整为堆结构
        int parent = (size - 1 - 1) / 2;
        for (int i = parent; i >= 0 ; i--) {
            // 向下调整的方法
            shiftDown(i);
        }
    }
   /**
    *向下调整
    */
    private void shiftDown(int parent) {
        if(parent < 0){
            return;
        }
        int child = parent * 2 + 1;
        while(child < size){
            if(child + 1 < size){
                if(elementDate[child + 1] > elementDate[child]){
                    child++;
                }
            }
            if(elementDate[parent] >= elementDate[child]){
                break;
            }
            swap(elementDate,parent,child);
            parent = child;
            child = parent * 2 + 1;
        }
    }

    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("数组为空");
        }
        int value = elementDate[0];
        swap(elementDate,0,size - 1);
        size--;
        shiftDown(0);
        return value;
    }
    public int peek(){
        return elementDate[0];
    }

    private boolean isEmpty() {
        return size == 0;
    }

    public void offer(int value){
        if(isFull()){
            elementDate =Arrays.copyOf(elementDate,elementDate.length * 2);
        }
        elementDate[size] = value;
        size++;
        shiftUp(size - 1);
    }

    private void shiftUp(int child) {
        if(child > size){
            return;
        }
        int parent = (child - 1) / 2;
        while(child > 0 && parent >= 0){
            if(elementDate[parent] >= elementDate[child]){
                break;
            }
            swap(elementDate,parent,child);
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    private boolean isFull() {
        return size == elementDate.length;
    }

    private void swap(int[] elementDate, int parent, int child) {
        int temp = elementDate[parent];
        elementDate[parent] = elementDate[child];
        elementDate[child] = temp;
    }

    public void display(){
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementDate[i]);
            if(i < size - 1){
                sb.append(",");
            }
        }
        sb.append("]");
        System.out.println(sb);
    }
}
